1. Field of the Invention
The invention relates to path planning and in particular to controlling the motion of an object in a changing environment.
2. Related Art
The field of path planning is one with many applications. The most common application is to controlling robots. Other applications include electronic maps, traffic control, emergency vehicle control, and emergency exit systems and vehicle maneuvering.
The path planning problem, as applied to robots, typically involves getting a robot from a start point to a goal point while avoiding obstacles. Automating multidimensional path planning for robots is one of the great historical problems of robotics.
The present invention is an improvement on the invention disclosed U.S. patent application Ser. No. 123,502, which is incorporated herein by reference as background material. That application disclosed, amongst other things, propagating cost waves through a configuration space by budding, using a space-variant metric.
After budding, some aspect of the configuration space may change, for instance, if an obstacle is removed or a goal added. In such a case, it may be inefficient to bud the entire configuration space again because only a small part of the configuration space may be affected.
T. Boult, "Updating Distance Maps when Objects Move", SPIE Vol. 852 Mobile Robots II (1987), pp. 232-237 deals with updating portions of a configuration space when objects move. This paper, however, does not discuss changing configuration spaces in the context of budding or in the context of space variant metrics. This paper also does not discuss the details of differentially changing a planned path when a transition cost changes.